"""
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。



示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。


提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成
"""


class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        # 我的想法还是遍历字符串，一个字符一个字符的比较，如果相同则继续，不同则返回结果
        first_str = strs[0]  # 参考字符串
        for i in range(len(strs[0])):
            char = first_str[i]
            for j in range(1, len(strs)):
                if i >= len(strs[j]) or strs[j][i] != char:
                    # python 的区间是 左闭右开
                    return first_str[:i]
        return first_str


# 开始测试
soultion = Solution()


def test():
    test_cases = [
        # 题面示例
        (["flower", "flow", "flight"], "fl"),
        (["dog", "racecar", "car"], ""),

        # 边界情况
        ([""], ""),
        (["", "abc"], ""),
        (["abc", ""], ""),
        (["", "", ""], ""),

        # 单字符串
        (["a"], "a"),
        (["abc"], "abc"),

        # 完全匹配
        (["abc", "abc", "abc"], "abc"),
        (["ab", "abc"], "ab"),
        (["abc", "ab"], "ab"),

        # 部分匹配
        (["apple", "apply", "app"], "app"),
        (["prefix1", "prefix2"], "prefix"),

        # 前缀嵌套
        (["longer", "long", "lon"], "lon"),
        (["abcd", "abef", "abgh"], "ab"),

        # 特殊场景
        (["a", "ab", "abc"], "a"),
        (["hello", "hexxo", "hey"], "he")
    ]

    for i, (strs, expected) in enumerate(test_cases):
        result = soultion.longestCommonPrefix(strs)
        assert result == expected, (
            f"测试 {i + 1} 失败: 输入 {strs}\n"
            f"预期: '{expected}'\n"
            f"实际: '{result}'\n"
        )
    print("✅ 所有测试通过！")


# 执行测试
test()
